import java.util.ArrayList;
import java.util.List;

public class Main {
    public int[] elem;
    public boolean contains(int toFind) {
        for (int i = 0; i < elem.length; i++) {
            if (elem[i] == toFind) {
                return true;
            }
        }
        return false;
    }
    public int indexof(int toFind) {
        for (int i = 0; i < elem.length; i++) {
            if (elem[i] == toFind) {
                return i;
            }
        }
        return -1;
    }

    //是否包含数据key
    /*public boolean contains(int key) {
        ListNode cur = head;
        while (cur != null) {
             if (cur.val == key) {
                 return true;
             }
             cur = cur.next;
        }
        return false;
    }*/

    public static int removeElement(int[] nums, int val) {
        int left = 0;
        int right = nums.length - 1;
        int k = 0;
        while(left < right) {
            while (left < right && nums[left] != val) {
                left++;
            }
            while (left < right && nums[right] == val) {
                right--;
            }
            int tmp = nums[left];
            nums[left] = nums[right];
            nums[right] = tmp;
        }
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != val) {
                k++;
            }
        }
        return k;
    }

    //杨辉三角
    public static List<List<Integer>> generate(int numRows) {
        List<List<Integer>> ret = new ArrayList<>();
        //添加第1行
        List<Integer> list0 = new ArrayList<>();
        list0.add(1);
        ret.add(list0);
        //从第2行开始
        for (int i = 1; i < numRows; i++) {
            List<Integer> tmpList = new ArrayList<>();
            //当前行的第1个
            tmpList.add(1);
            //上一行的list
            List<Integer> prevRow = ret.get(i - 1);
            //当前行的中间值
            for (int j = 1; j < i; j++) {
                int val1 = prevRow.get(j);
                int val2 = prevRow.get(j - 1);
                tmpList.add(val1 + val2);
            }
            //当前行的最后1个
            tmpList.add(1);
            ret.add(tmpList);
        }
        return ret;
    }

    public static void main2(String[] args) {
        List<List<Integer>> ret = generate(5);
        System.out.println(ret);
    }


    //   还未完成！！！
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = 0;
        while (i < nums1.length) {
            while (nums1[i] <= nums2[i]) {
                i++;
            }
            nums1[i] = nums2[1];
            i++;
        }
    }

    public int removeDuplicates(int[] nums) {
        int k = 1;
        int len = nums.length;
        for(int i = 1; i < len; i++){
            if(nums[i] != nums[i-1]) {
                nums[k] = nums[i];
                k++;
            }
        }
        return k;
    }

    public static void main1(String[] args) {
        int[] nums = {0,1,2,2,3,0,4,2};
        int ret = removeElement(nums,2);
        System.out.println(ret);
    }
}